package 动态规划.规划兼职工作;

import java.util.Arrays;
import java.util.Comparator;

//开始时间，结束时间，收益，时间上重叠的两份兼职不能同时进行
class jobs{
    int start,end,profit;
    jobs(int s,int e,int p){
        start=s;
        end=e;
        profit=p;
    }
}

class Solution
{
    public static void main(String[] args)
    {
        int[] startTime = new int[]{1, 2, 3, 3};
        int[] endTime = new int[]{3,4,5,6};
        int[] profit = new int[]{50, 10, 40, 70};
        System.out.println(jobScheduling(startTime, endTime, profit));
    }
    public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n=startTime.length;

        int dp[]=new int[n+1];//当有前n个工作可以选时，收益的最大值

        jobs[] job=new jobs[n];

        for(int i=0;i<n;i++)
            job[i]=new jobs(startTime[i],endTime[i],profit[i]);

        Arrays.sort(job, Comparator.comparingInt(o->o.end));//按照结束时间排序

        for(int i=0;i<n;i++)
            dp[i]=job[i].profit;

        for(int i=1;i<n;i++)
        {
            dp[i] = Math.max(dp[i-1], job[i].profit);

            for(int j=i-1;j>=0;j--)//j=i-1
                //反向，因为相当于01背包，只有一个工作,j是前一个，i是后一个
                if(job[j].end<=job[i].start)//前一个的end结束时间在后一个的start开始时间之前。也就是不冲突
                {
                    dp[i]=Math.max(dp[i],dp[j]+job[i].profit);
                    break;
                }
        }
        return dp[n-1];
    }
    public int jobScheduling1(int[] startTime, int[] endTime, int[] profit)
    {
        int n = startTime.length;

        int[][] nums = new int[n][3];
        for(int i = 0;i<n;i++)
        {
            nums[i][0] = startTime[i]; //开始时间
            nums[i][1] = endTime[i]; //结束时间
            nums[i][2] = profit[i];  //价值
        }

        Arrays.sort(nums,(a,b)->(a[1]-b[1]));  //按照结束的时间排序，即按照第一列排序

        //定义动态规化数组,p[i]是以当前任务 i 为最后一个任务可以取得的最大收益
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0][2];
        for (int i = 2; i <= n; i++)
        {
            int opt_index = 0;
            for (int j = i-1; j > 0; j--)
            {
                // 计算对于当前任务，最近可以完成的上一个任务的下标是什么
                // 即之前任务结束时间小于等于当前任务开始时间
                // 求对于选择做当前任务，再加上前一个可以做的任务的最大收益，返回opt[j]+task[i][2]
                if (nums[j-1][1] <= nums[i-1][0])
                {
                    opt_index = j;
                    break;
                }
            }
            dp[i] = Math.max(dp[i-1],dp[opt_index]+nums[i-1][2]);
        }
        return dp[n];
    }

//    作者：user9563G
//    链接：https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/solution/dong-tai-gui-hua-by-user9563g/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
//
//作者：mo_yu
//        链接：https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/solution/java-dong-tai-gui-hua-by-zhi-94/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
